41. First Missing Positive

Similar Question

leading to the advanced question

Solution Tips

方案一: Arithmetic-progression

var firstMissingPositive = function(nums) {
    // 要 O(n) 的就无法 sort 了
    // 等差数列的原地标记法，不能应付含有负数的情况，但是其实负数本身也不影响结果吧？
    // 把负数过滤掉就好了？
    nums = nums.filter((val) => val > 0);

    // 过滤后再执行原地标记即可
    for (let i = 0; i < nums.length; i++) {
        const num = nums[i];
        const itemIndex = Math.abs(num) - 1;
        if (nums[itemIndex] > 0) {
            nums[itemIndex] = -nums[itemIndex];
        }
    }

    for (let i = 0; i < nums.length; i++) {
        const num = nums[i];
        if (num > 0) {
            // 该项依然是正数，说明对应的 index + 1 的 num 不存在
            return i + 1;
        }
    }

    // 循环内没有 return，说明第一个 missing 的 index 为数组长度 + 1
    return nums.length + 1;
};

console.log(firstMissingPositive([1,2,0]))
console.log(firstMissingPositive([3,4,-1,1]))
console.log(firstMissingPositive([7,8,9,11,12]))

参考之前的题目，这里也可以用置换法，目前来看置换和负数标记适用的场景是一样的， 置换反而还难理解一点。